/*
给你一个长度为N的链表。
N很大，但你不知道N有多大。
你的任务是从这N个元素中随机取出k个元素。
你只能遍历这个链表一次。
你的算法必须保证取出的元素恰好有k个，
且它们是完全随机的（出现概率均等）。 
*/

#include "junix.h"
using namespace std;

int k_rand(int s[], int N, int d[], int k) {
	assert(N>=k);
	std::copy(s,s+k,d);

	for (int i=k;i<N;i++) {
		int kr = rand()%i;
		if (kr<k)
			d[kr]=s[i];
	}
}	

int main(int argc, char **argv)
{
}
